﻿//Author: Paweł Kaftan
using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography;
using System.IO;
using System.Reflection;

namespace HamiltonianCycle
{
    partial class Program
    {
        static List<int> BruteForceSearchAlgorithm(List<int>[] graphArgument)
        {
            List<int> HamiltonianCycle = new List<int>();
            bool endOfFunction = false;
            BruteForceSearch(0, ref endOfFunction, HamiltonianCycle, graphArgument);
            return HamiltonianCycle;
        }
        static void BruteForceSearch(int a, ref bool endOfFunction, List<int> HamiltonianCycle, List<int>[] graphArgument)
        {
            if (!endOfFunction)
            {
                HamiltonianCycle.Add(a);
                if (HamiltonianCycle.Count == graphArgument.Length && graphArgument[HamiltonianCycle.Last()].Contains(HamiltonianCycle[0]))
                    endOfFunction = true;
                for (int b = 0; b < graphArgument[a].Count; ++b)
                    if (!HamiltonianCycle.Contains(graphArgument[a][b]))
                        BruteForceSearch(graphArgument[a][b], ref endOfFunction, HamiltonianCycle, graphArgument);
                if (!endOfFunction)
                    HamiltonianCycle.Remove(a);
            }
        }
        static bool CheckCorrectnessOfFoundHamiltonianCycle(List<int>[] graphArgument, List<int> HamiltonianCycleArgument)
        {
            List<int> vertices = new List<int>();
            vertices.AddRange(HamiltonianCycleArgument);
            vertices.Sort();
            if (HamiltonianCycleArgument.Count != graphArgument.Length)
                return false;
            if (vertices[0] == vertices[1])
                return false;
            for (int a = 1; a < graphArgument.Length; ++a)
                if (vertices[a - 1] == vertices[a])
                    return false;
            for (int a = 0; a < HamiltonianCycleArgument.Count - 1; ++a)
                if (!graphArgument[HamiltonianCycleArgument[a]].Contains(HamiltonianCycleArgument[a + 1]))
                    return false;
            if (!graphArgument[HamiltonianCycleArgument.Last()].Contains(HamiltonianCycleArgument[0]))
                return false;
            return true;
        }
        static void WriteGraph(List<int>[] graphArgument, string name = "")
        {
            Console.WriteLine(name);
            int a = -1;
            foreach (List<int> List in graphArgument)
            {
                ++a;
                if (a > 9)
                    Console.Write(a.ToString() + ": ");
                else
                    Console.Write(" " + a.ToString() + ": ");
                for (int b = 0; b < graphArgument.Length; ++b)
                    if (graphArgument[a].Contains(b))
                        Console.Write(b.ToString() + " ");
                    else
                    {
                        if (b < 10)
                            Console.Write("-" + " ");
                        else
                            Console.Write("--" + " ");
                    }
                Console.WriteLine("");
            }
        }
        static void WriteCycle(List<int> cycleArgument)
        {
            string cycle = "";
            foreach (int a in cycleArgument)
            {
                cycle += a + "|";
            }
            Console.WriteLine(cycle + "      ");
        }
        static List<int>[] CreateGraph(int numberOfVerticesArgument, double density, bool HamiltonianCycleExists, bool directed, bool moreRandomNumbers)
        {
            if (!directed)  //true - if you want to examine undirected graph
                density *= 0.5;
            List<int>[] graph = new List<int>[numberOfVerticesArgument];
            for (int a = 0; a < numberOfVerticesArgument; ++a)
                graph[a] = new List<int>();
            if (HamiltonianCycleExists) //true - if you want to examine graph with Hamiltonian cycle
            {
                List<int> HamiltonianCycle = new List<int>();
                for (int a = 0; a < numberOfVerticesArgument; ++a)
                    HamiltonianCycle.Add(a);
                for (int a = 0; a < numberOfVerticesArgument * 10; ++a)
                {
                    using (RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider())
                    {
                        Random r = new Random();
                        byte[] data = new byte[4];
                        rng.GetBytes(data);
                        int index = BitConverter.ToInt32(data, 0);
                        if (index < 0)
                            index *= -1;
                        try
                        {
                            int number = HamiltonianCycle[index % numberOfVerticesArgument];
                            HamiltonianCycle.RemoveAt(index % numberOfVerticesArgument);
                            HamiltonianCycle.Insert(r.Next(0, numberOfVerticesArgument), number);
                        }
                        catch { }
                    }
                }
                for (int a = 0; a < HamiltonianCycle.Count - 1; ++a)
                    graph[HamiltonianCycle[a]].Add(HamiltonianCycle[a + 1]);
                graph[HamiltonianCycle.Last()].Add(HamiltonianCycle.First());
            }
            List<int> degreesOfVertices = new List<int>();
            Random random = new Random();
            int max = Convert.ToInt32((double)density * (double)numberOfVerticesArgument);
            degreesOfVertices.AddRange(GetRandomNumbers(random.Next(0, max), max, moreRandomNumbers).Take(numberOfVerticesArgument)); //Found here - http://stackoverflow.com/a/4858877
            for (int a = 0; a < numberOfVerticesArgument; ++a)
            {
                List<int> vertices = new List<int>();
                vertices.AddRange(GetRandomNumbers(0, numberOfVerticesArgument, moreRandomNumbers).Distinct().Take(degreesOfVertices[a])); //Found here - http://stackoverflow.com/a/4858877
                for (int b = 0; b < vertices.Count; ++b)
                    graph[a].Add(vertices[b]);
            }
            if (!directed) //true - if you want to examine undirected graph
            {
                for (int a = 0; a < numberOfVerticesArgument; ++a)
                    for (int b = 0; b < numberOfVerticesArgument; ++b)
                        if (graph[a].Contains(b))
                            graph[b].Add(a);
            }
            for (int a = 0; a < numberOfVerticesArgument; ++a)
                graph[a].Sort();
            return graph;
        }
        static IEnumerable<int> GetRandomNumbers(int min, int max, bool moreRandomNumbers) //Found here - http://stackoverflow.com/a/4858877
        {
            var rand = new Random();
            if (moreRandomNumbers)
                rand = new Random((int)Guid.NewGuid().GetHashCode() % 50000);
            while (true)
            {
                yield return rand.Next(min, max);
            }
        }
        static List<int>[] LoadGraphFromFile(string filename, string path = "")
        {
            try
            {
                int numberOfVertices = System.IO.File.ReadLines(path + filename).Count();
                List<int>[] graph = new List<int>[numberOfVertices];
                graph = new List<int>[numberOfVertices];
                for (int a = 0; a < numberOfVertices; ++a)
                    graph[a] = new List<int>();
                string line;
                StreamReader file = new StreamReader(path + filename);
                while ((line = file.ReadLine()) != null)
                {
                    string[] vertices = line.Split(new char[] { ' ', ':' }, StringSplitOptions.RemoveEmptyEntries);
                    List<int> list = new List<int>();
                    for (int b = 1; b < vertices.Length; ++b)
                        if (!graph[Convert.ToInt32(vertices[0])].Contains(Convert.ToInt32(vertices[b])))
                            graph[Convert.ToInt32(vertices[0])].Add(Convert.ToInt32(vertices[b]));
                }
                file.Close();
                return graph;
            }
            catch
            {
                Console.WriteLine("An error occurred. Graph was not loaded from file.");
                Console.ReadKey();
                return null;
            }
        }
        static void SaveGraphToFile(string filename, List<int>[] graphArgument, string path = "")
        {
            Directory.CreateDirectory(Path.GetDirectoryName(Assembly.GetEntryAssembly().Location) + path);
            try
            {
                StreamWriter writer = new StreamWriter(Path.GetDirectoryName(Assembly.GetEntryAssembly().Location) + path + "//" + filename);
                for (int a = 0; a < graphArgument.Length; ++a)
                {
                    List<int> Vertices = new List<int>();
                    string line = a.ToString() + ": ";
                    foreach (int b in graphArgument[a])
                        line += b.ToString() + " ";
                    writer.WriteLine(line);
                }
                writer.Close();
            }
            catch
            {
                Console.WriteLine("An error occurred. Graph was not saved to file.");
                Console.ReadKey();
            }
        }
        static int GraphDensityInPercent(List<int>[] graphArgument)
        {
            double sum = 0;
            foreach (List<int> list in graphArgument)
                sum += list.Count();
            double average = sum / Convert.ToDouble(graphArgument.Length);
            return Convert.ToInt32((average / graphArgument.Length) * 100.0);
        }
        static int NumberOfEdges(List<int>[] graphArgument)
        {
            int numberOfEdges = 0;
            foreach (List<int> list in graphArgument)
                numberOfEdges += list.Count;
            return numberOfEdges;
        }
    }
}